package com.example.demo.leetcode;

import java.util.HashSet;
import java.util.Set;

/**
 * https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/?envType=study-plan-v2&envId=top-100-liked
 *
 * @author WangYX
 * @version 1.0.0
 * @date 2024/02/29 16:08
 */
public class _3_无重复字符的最长子串 {

    public static void main(String[] args) {
        String s = "abcabcbb";
        String s1 = "au";
        String s3 = "bbbbb";
        String s4 = "pwwkew";
        String s5 = "aab";
        int i = lengthOfLongestSubstring1(s4);
        System.out.println(i);
    }

    /**
     * 方法一：暴力求解
     * <p>
     * 时间复杂度 O(N^3)
     * 空间复杂度 O()
     *
     * @param s
     * @return
     */
    public static int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int num = 1;
        int length = s.length();

        int start = 0;
        Set<Character> set = new HashSet<>();
        int index = 0;
        //窗口宽度
        for (int i = 2; i <= length; i++) {
            if (!set.isEmpty()) {
                if (index + 1 < length) {
                    boolean add = set.add(s.charAt(index + 1));
                    if (!add) {
                        set.clear();
                        start++;
                    } else {
                        index++;
                        num = i;
                    }
                }
            }
            if (set.isEmpty()) {
                //用当前窗口宽度遍历数组
                int l = length - i;
                for (int j = start; j <= l; j++) {
                    //判断该窗口宽度内的子串是否有重复的字符
                    boolean flag = true;
                    for (int k = j; k <= j + i - 1; k++) {
                        boolean add = set.add(s.charAt(k));
                        if (!add) {
                            //字符重复了
                            flag = false;
                            set.clear();
                            break;
                        }
                        index = k;
                    }

                    //如果没有重复的字符，则说明当前长度满足条件，跳出当前循环
                    if (flag) {
                        num = i;
                        break;
                    }

                }
            }
        }
        return num;
    }


    /**
     * 方法二：
     *
     * @author WangYX
     * @date 2024/02/29 17:27
     * @version 1.0.0
     */
    public static int lengthOfLongestSubstring1(String s) {

        // 哈希集合，记录每个字符是否出现过
        Set<Character> occ = new HashSet<Character>();
        int n = s.length();

        // 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
        int rk = -1;
        int ans = 0;
        for (int i = 0; i < n; ++i) {

            if (i != 0) {
                // 左指针向右移动一格，移除一个字符
                occ.remove(s.charAt(i - 1));
            }

            while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) {
                // 不断地移动右指针
                occ.add(s.charAt(rk + 1));
                ++rk;
            }

            // 第 i 到 rk 个字符是一个极长的无重复字符子串
            ans = Math.max(ans, rk - i + 1);

        }

        return ans;
    }
}
